package recursion;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class D230727 {
    // 没有重复项数字的全排列
    // 存所有排列的集合
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        // 存一种排列
        LinkedList<Integer> list = new LinkedList<>();
        // 递归进行
        backTrack(num,list);
        return res;
    }
    public void backTrack(int[] num, LinkedList<Integer> list){
        if (list.size() == num.length) {
            // 一个排列结果
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < num.length; i++) {
            if (list.contains(num[i])) {
                // 已存在排列中
                continue;
            }
            // 选择该数
            list.add(num[i]);
            // 继续寻找
            backTrack(num, list);
            // 撤销
            list.removeLast();
        }
    }



    // 有重复项数字的全排列
    // 用于标记是否访问过
    boolean []mark;
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        // 存储总的返回结果集
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        // 存储一个合法全排列
        LinkedList<Integer> track = new LinkedList<>();

        mark = new boolean[num.length];
        // 因为存在重复项，为了更好的处理，将数组先排序
        Arrays.sort(num);

        backtrack(num,res,track);

        return res;
    }
    public void backtrack(int[] num, ArrayList<ArrayList<Integer>> res, LinkedList<Integer> track){
        // 若找到一个全排列，则将它加进结果集中，然后返回(回溯)
        if(track.size() == num.length){
            res.add(new ArrayList<Integer>(track));
            return;
        }
        for(int i = 0; i < num.length; i++){
            // 当前元素被访问过
            // 当i>0 && 当前元素等于上一个元素
            // && 上一个没访问过(没访问过证明是回溯后将前面的置为false，
            // 所以此时避免重复得用 !mark[i-1] 满足要求然后跳过该数字)

            // arr[1,1,1,2,3]
            // 1,1,1  1,1,2  1,1,3  前面两次回溯得到三个结果
            // 接下来再进行回溯，此时mark[1]被置为false
            // 此时按道理应该遍历到 arr[2] 这个位置
            // 但是我们发现arr[2]==arr[1]，并且此时mark[1]==false
            // 证明它的已经访问过然后回溯的，所以我们跳过arr[2],直接从arr[3]开始
            // 也就是说此时得到全排列的结果将会是 1,2,1 1,2,3 而不再是 1,1 ··· 这些重复的了
            if(mark[i] || i>0 && num[i] == num[i-1] && !mark[i-1]){
                continue;
            }
            // 添加进全排列数组中
            track.add(num[i]);
            // 标记为已经访问
            mark[i] = true;
            // 继续寻找下一个数
            backtrack(num,res,track);
            // 将上一次全排列的结果中，最后一个数移除掉
            track.removeLast();
            // 移除掉的数置为 未访问
            mark[i] = false;
        }
    }



    // 岛屿数量
    // 遇到一个岛屿，递归与它相连的岛屿，进行标记.
    public int solve (char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    backtrack(grid, i, j);
                }
            }
        }
        return count;
    }
    private void backtrack(char[][] grid, int i , int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') {
            return;
        }
        // 标记已经记录过的岛屿
        grid[i][j] = '0';
        int[][] direct = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int k = 0; k < 4; k++) {
            backtrack(grid, i + direct[k][0], j + direct[k][1]);
        }
    }



    // 字符串的排列
    // 与有重复项数字的全排列，思路一模一样
    boolean[] vis;  // 标记每个位置的字符是否被使用过
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> res = new ArrayList<String>();
        if(str == null || str.length() == 0)
            return res;
        // 转字符数组
        char[] charStr = str.toCharArray();
        // 按字典序排序
        Arrays.sort(charStr);
        vis = new boolean[str.length()];
        StringBuffer temp = new StringBuffer();
        // 递归获取
        recursion(res, charStr, temp);
        return res;
    }
    public void recursion(ArrayList<String> res, char[] str, StringBuffer temp){
        // 临时字符串满了，加入结果集，回溯
        if(temp.length() == str.length){
            res.add(new String(temp));
            return;
        }
        // 遍历所有元素选取一个加入
        for(int i = 0; i < str.length; i++){
            // 如果该元素已经被加入了则不需要再加入了
            if(vis[i])
                continue;
            if(i > 0 && str[i - 1] == str[i] && !vis[i - 1])
                // 当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用过了
                continue;
            // 标记为使用过
            vis[i] = true;
            // 加入临时字符串
            temp.append(str[i]);
            recursion(res, str, temp);
            // 回溯
            vis[i] = false;
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}
